{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Paillier's encryption Scheme\n",
    "=========================="
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The Paillier crypto system, invented by and named after Pascal Paillier in 1999, is a probabilistic asymmetric algorithm for public key cryptography. The problem of computing $n-th$ residue classes is believed to be computationally difficult. The decisional composite residuosity assumption is the intractability hypothesis upon which this cryptosystem is based. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Key Generation:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. Choose two large prime numbers $P$ and $Q$ randomly and indenpendently of each other such that $gcd(PQ, (P-1)(Q-1))=1$. This property is assured if both primes are equal lenth."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from klefki.const import (SECP256K1_P as P, SECP256K1_N as Q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "from math import gcd\n",
    "\n",
    "assert gcd(P * Q, (P - 1) * (Q - 1)) == 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2. Compute $N=PQ$ and $\\lambda(N)=lcm(P-1, Q-1)$ be the Carmichael function of N."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "from klefki.numbers import lcm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "N = P * Q\n",
    "Lam = lcm(P - 1, Q - 1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "3. Select random integer $\\Gamma$ where $\\Gamma \\in \\mathbf{Z}_{n^2}^*$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "from random import randint\n",
    "from klefki.types.algebra.utils import randfield\n",
    "from klefki.types.algebra.meta import field\n",
    "\n",
    "F = field(N, \"N\")\n",
    "DF = field(N**2, \"N^2\")\n",
    "G = randfield(DF)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "4. Ensure $n$ devides the order of $g$ by checking the existence of the following modular multiplicative inverse: \n",
    "\n",
    "$$\n",
    "\\mu = (L(G^{\\lambda(N)}\\mod N^2))^{-1} \\mod \\ N\n",
    "$$\n",
    "\n",
    "Where $L$ be a function defined over the set $\\{x\\in \\mathbf{Z}_{N^2}: x=1 \\ mod \\ N\\}$ computed as\n",
    "\n",
    "$$\n",
    "L(x) = \\frac{x-1}{N}\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "L = lambda x: (x - 1) // N"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The public key is $(N, \\Gamma)$ and the secret key is $(\\lambda(N))$\n",
    "\n",
    "If using p,q of equivalent length, a simpler variant of the above key generation steps would be to set $g = n + 1 , λ = φ ( n )$, and $\\mu = φ(n)^{-1}\\ mod \\ n$, where $φ(n)=(p-1)(q-1)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "PrivKey: 2234634654990432849929004166367641021238215826767191291571707378398254532167475902984296517123225539202576657105730699764493290075143829571044458305451072\n"
     ]
    }
   ],
   "source": [
    "print(\"PrivKey: %s\" % Lam)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "PubKey: 13407807929942597099574024998205846127429294960603147749430244270389527193005087002084253735130200377185477318450090306135904455919285040173416176828872431; 77035126901414243466593033818616330970366679968094154722572700152333391747783504498549422681480857084131841310916380433218514709109231164061290704333180832878606535936787048649862356920125008479743359336912545136561115652209816489026998639931414361265240792280633335547102958672135420024259094083644382006236\n"
     ]
    }
   ],
   "source": [
    "print(\"PubKey: %s; %s\" % (N, G))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Encryption:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To Encrypt a message $M \\in Z_N$, select $R \\in_R Z_N^*$ and return $c=\\Gamma^M R^N\\ mod \\ N^2$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "import math\n",
    "m = random.randint(0, N)\n",
    "assert 0 <= m < N\n",
    "\n",
    "r = DF(random.randint(0, N))\n",
    "assert math.gcd(r.value, N) == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "c = G**m * r**N"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Ciphtertext Text: 7016628710028750763220234799772443961517829663536340494877375384716387806068796190029061065289125116984936899123466377581433183611140917487456099941786219495981415910545327007385914304277320973108642790490995523777576032108671309475901939594111754694043435450378428378425126512315421950443099829027922257557\n"
     ]
    }
   ],
   "source": [
    "print(\"Ciphtertext Text: %s\" % c)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Decryption:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To decrypt a ciphertext $c \\in Z_N$, let $L$ be a function defined over the set $\\{u\\in Z_{N^2}: u=1 \\ mod \\ N\\}$ computed as $L(u) = \\frac{u-1}{N}$. Then the decryption of $c$ is computed as\n",
    "\n",
    "$$\n",
    "\\frac{L(c^{\\lambda(N)}\\ mod\\ N^2)}{L(\\Gamma^{\\lambda(N)}\\ mod\\ N^2)}\\ mod\\ N\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The function $L$ is used to compute $i$ from $(1+n)^i \\mod n^2$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "assert F(m) == F(L((c ** Lam).value)) * ~F(L(pow(G, Lam).value))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Homomorphic"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "E(m_i) \\in Z_{N^2}\\\\\n",
    "m_i \\in Z_N\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Homomorphic addition"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "from klefki.crypto.paillier import Paillier\n",
    "from klefki.const import (SECP256K1_P as P, SECP256K1_N as Q)\n",
    "from klefki.types.algebra.utils import randfield"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "Pai = Paillier(P, Q)\n",
    "E = Pai.E\n",
    "D = Pai.D\n",
    "\n",
    "Lam = Pai.privkey\n",
    "N, G = Pai.pubkey\n",
    "\n",
    "F = field(N, \"N\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "m1, m2 = randfield(F), randfield(F)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* The product of two ciphertexts will decrypt to the sum of their corresponding plaintexts,\n",
    "$$\n",
    "D(E(m_1, r_1) \\circ E(m_2, r_2)) = m_1 + m_2\\\\\n",
    "$$\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "assert D(E(m1) * E(m2)) == D(E(m1)) + D(E(m2)) == m1 + m2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* The product of a ciphertext with a plaintext raising $g$ will decrypt to the sum of the corresponding plaintexts.\n",
    "\n",
    "\n",
    "$$\n",
    "D(E(m_1, r_1)\\circ g^{m_2}) = m_1+m_2\\\\\n",
    "$$\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "D(E(m1) * (G ** m2)) == m1 + m2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Homomorphic multiplication"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* An encrypted plaintext raised to the power of another plaintext will decrypt to the product of the two plaintexts,"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "D(E(m_1, r_1)^{m_2}) = m_1m_2\\\\\n",
    "D(E(m_2, r_2)^{m_1}) = m_1m_2\\\\\\\\\n",
    "$$\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "D(E(m1)**m2) == m1 * m2 == D(E(m2)**m1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "More generally, an encrypted plaintext raised to a constant k will decrypt to the product of the plaintext and the constant,\n",
    "\n",
    "$$\n",
    "D(E(m, r)^{k}) = km\n",
    "$$\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "k = randfield(F)\n",
    "m = randfield(F)\n",
    "\n",
    "\n",
    "D(E(m) ** k) == k * m"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Ref\n",
    "\n",
    "* Wikipedia: Pillier Cryptosystem https://en.wikipedia.org/wiki/Paillier_cryptosystem\n",
    "\n",
    "\n",
    "* Encryption Performance Improvementsof the Paillier Cryptosystem https://eprint.iacr.org/2015/864.pdf\n",
    "\n",
    "\n",
    "* Stackoverflow - Paillier algorithm encryption https://stackoverflow.com/questions/29217630/paillier-algorithm-encryption\n",
    "\n",
    "* RSA cryptosystem relation between lambda and phi. https://math.stackexchange.com/questions/3249362/rsa-cryptosystem-relation-between-lambda-and-phi"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}